1. Field of the Invention
The present invention relates wireless communication systems, and in particular, to an apparatus and method for transmitting and receiving data in a communication system using Low Density Parity Check (LDPC) codes.
2. Description of the Related Art
Generally, in communication systems, a data transmission/reception process can be outlined as: data generated in a source of a transmission side is wirelessly transmitted over a channel after undergoing source coding, channel coding, interleaving, and modulation and after receiving the wirelessly transmitted signal at the reception side, the reception side performs demodulation, deinterleaving, channel decoding, and source decoding on the received signal.
However, in communication systems, distortion of signals occurs due to various noises, fading phenomena and Inter-Symbol Interference (ISI) of within and among the different transmission channels. In the high-speed digital communication system requiring high data throughput and high reliability, such as next-generation mobile communication, digital broadcasting and portable internet, a technology for coping with signal distortion caused by the noises, fading and ISI is indispensable. The channel coding and interleaving are typical of technologies that are used to mitigate the effects of noise fading and ISI in distorting transmitted signals.
Interleaving is used for minimizing a data transmission loss and increasing a channel coding effect, as is more fully described below, by distributing a damaged portion of desired transmission bits over several places without concentrating the damaged portion on a single spot. The concentration of distorted bits is known in the art as a burst error which frequently occurs while a signal passes through a fading channel, and the distribution of the damaged portion over several places is used reduce the occurrence of a burst error within the transmission stream
Channel coding is popularly used as a method for allowing a reception side to check signal distortion caused by noises, fading and ISI, and to efficiently restore the distorted signal, thereby increasing communication reliability. Codes used for channel coding are called Error-Correcting Codes (ECCs) as they enable the reception side to correct errors that have been detected. Intensive research is being conducted on various types of error-correcting codes.
The well-known error-correcting codes include block codes, convolutional codes, turbo codes, and LDPC codes. Since the present invention is directed to a communication system using LDPC codes, a brief description of the LDPC codes is provided.
The LDPC code is known as a code that can minimize information loss probability though it cannot guarantee perfect transmission of signals. The LDPC code, which was first proposed in 1960s, is the first channel coding code capable of transmitting signals at a rate approximating the maximum data rate (i.e., the Shannon limit) which is known in Shannon's channel coding theory. The LDPC code could not be substantially used since the -technology level in the 1960s was not sufficiently advanced to realize the LDPC code. However, as the LDPC code was rediscovered around 1996 owing to the succeeding information theory and the progress of technologies, a study is being made of characteristics of the LDPC code showing that its complexity does not considerably increase even though it uses iterative decoding, and a study is also being made of a method for generating the LDPC code. The LDPC code, together with the turbo code, is being suggested as a very superior error-correcting code useful for the next-generation mobile communication system. The LDPC code is commonly expressed using a graph representation, and its many characteristics can be analyzed using methods based on graph theory, algebra, and probability theory. Generally, a graph model of channel codes is useful for descriptions of codes, and if information on each coded bit corresponds to a vertex in the graph and relationships between the coded bits correspond to edges in the graph, the vertexes can be considered as communication networks that exchange predetermined messages through the edges, making it possible to derive a natural decoding algorithm. For example, decoding algorithms induced from the trellis that can be regarded as a kind of graph can include the well-known Viterbi algorithm and Bahl, Cocke, Jelinek and Raviv (BCJR) algorithm. As such codes are well known in the art, a discussion of same need not be provided herein.
The LDPC code is generally defined as a parity-check matrix, and can be represented using a bipartite graph, commonly referred to as a Tanner graph. The bipartite graph means that vertexes constituting the graph are divided into two different types, and for the LDPC code, the vertexes of two different types are variable nodes and check nodes. The variable nodes one-to-one correspond to coded bits.
With reference to FIGS. 1 and 2, a description is illustrated of an exemplary graphical representation of the LDPC code.
FIG. 1 is a diagram illustrating a parity-check matrix H1 of an LDPC code. In FIG. 1, a parity-check matrix of an LDPC code, composed of 4 rows and 8 columns, is considered. The matrix of FIG. 1 represents an LI)PC code for generating a length-8 codeword, as it has 8 columns. That is, the columns correspond to 8 coded bits. Although, the number of columns shown herein of length eight (8), it would be recognized by those skilled in the art that the number of columns may be increased or decreased without altering the scope of the invention.
FIG. 2 illustrates a graphical representation for a parity-check matrix H1 of an LDPC code. That is, FIG. 2 is a diagram illustrating a Tanner graph corresponding to check matrix H1 of FIG. 1. Referring to FIG. 2, the Tanner graph of the LDPC code is composed of 8 variable nodes x1 (202), x2 (204), x3 (206), x4 (208), x5 (210), x6 (212), x7 (214) and x8 (216), and 4 check nodes 218, 220, 222 and 224. Here, an ith column and a jth row of the parity-check matrix H1 of the LDPC code corresponds to a variable node xi and a jth check node, respectively. A value of 1, or a non-zero value, at the point where an ith column and a jth row of the parity-check matrix H1 of the LDPC code intersect infers that an edge exists between the variable node xi and the jth check node on the Tanner graph as shown in FIG. 2.
In the Tanner graph of the LDPC code, degrees of variable nodes and check nodes refers to the number of edges connected to the corresponding nodes, and the degree is equal to the number of non-zero entries in a column or row associated with the corresponding node in the parity-check matrix of the LDPC code. For example, in FIG. 2, degrees of the variable nodes x1 (202), x2 (204), x3 (206), x4 (208), x5 (210), x6 (212), x7 (214) and x8 (216) are 4, 3, 3, 3, 2, 2, 2 and 2, respectively, and degrees of the check nodes 218, 220, 222 and 224 are 6, 5, 5 and 5, respectively. In addition, the number of non-zero entries in the columns of the parity-check matrix H1 of FIG. 1, corresponding to the variable nodes of FIG. 2, are coincident with the degrees 4, 3, 3, 3, 2, 2, 2 and 2 in that order, and the number of non-zero entries in the rows of the parity-check matrix H1 of FIG. 1, corresponding to the check nodes of FIG. 2, are coincident with the degrees 6, 5, 5 and 5 in that order.
As described above, coded bits are in a one-to-one correspondence with columns of the parity-check matrix, and a one-to-one correspondence to variable nodes on the Tanner graph. In addition, degrees of variable nodes that in a one-to-one correspondence to the coded bits are referred to as degrees of coded bits.
For the LDPC code, it is known that higher-degree codeword bits are superior in decoding performance to lower-degree codeword bits. This is because compared with lower-degree variable nodes, higher-degree variable nodes acquire more information through iterative decoding, contributing to improvement of decoding performance.
The LDPC code has been described so far. A description will now be made of a signal constellation to which Quadrature Amplitude Modulation (QAM) is applied, QAM is a high-order modulation scheme commonly used in communication systems. A QAM-modulated symbol is composed of a real part and an imaginary part, and various modulation symbols can be formed by differentiating magnitude and sign of the real part and the imaginary part. To find out characteristics of QAM, QAM will be described together with Quadrature Phase Shift Keying (QPSK) modulation.
FIG. 3A is a schematic diagram of a signal constellation for a general QPSK modulation scheme. In the constellation, y0 determines a sign of a real part, and y1 determines a sign of an imaginary part. That is, when y0=0, a sign of the real part is plus (+), and when y0=1, a sign of the real part is minus (−). In addition, when y1=0, a sign of the imaginary part is plus (+), and when y1=1, a sign of the imaginary part is minus (−). Since y0 and y1 are sign indication bits indicating signs of the real part and the imaginary part, respectively, they are equal in error occurrence probability. Thus, for QPSK modulation, constituent bits of (y0, y1) corresponding to one modulation signal are equal in reliability. For y0,q and y1,q, the second index ‘q’ refers to a qth output of a modulation signal-constituting bit.
FIG. 3B is a schematic diagram of a signal constellation for a general 16-QAM modulation scheme. Constituent bits of (y0, yi, y2, y3) corresponding to one modulation signal have the following definitions. Constituent bit y0 and y2 determine sign and magnitude of a real part, respectively, and constituent bit y1 and y3 determine sign and magnitude of an imaginary part, respectively. In other words, y0 and y1 determine signs of a real part and an imaginary part of a signal, and y2 and y3 determine magnitudes of a real part and an imaginary part of a signal. Since distinguishing sign of a modulated signal is easier than distinguishing magnitude, error occurrence probability for y2 and y3 is higher than error occurrence probability at y0 and y1. Therefore, no-error probabilities, or reliabilities, of constituent bits, are R(y0)=R(y1)>R(y2) R(y3). Here, R(y) represents reliability for a constituent bit yk, where k=0-3. Unlike the QPSK modulation signal, the QAM modulation signal (y0, y1, y2, y3) has a characteristic that constituent bits are different in reliability.
In 16-QAM modulation, wherein 4 bits constitute a signal, 2 bits determine signs of a real part and an imaginary part of the signal, and 2 bits only need to represent magnitudes of the real part and the imaginary part of the signal, so an order of (y0, y1, y2, y3) and a role of each constituent bit are subject to change.
FIG. 3C is a schematic diagram of a signal constellation for a general 64-QAM modulation scheme. In this case, constituent bits of (y0, y1, y2, y3, y4, y5) corresponding to one modulation signal, wherein bits y0, y2 and y4 determine sign and magnitude of a real part, and bits y1, y3 and y5 determine sign and magnitude of an imaginary part. Here, y0 and y1 determine signs of the real part and the imaginary part, respectively, and y2, y3, y4 and y5 determine magnitudes of the real part and the imaginary part, respectively. Since distinguishing sign of a modulated signal is easier than distinguishing magnitude, reliabilities of y0 and y1 are higher than reliabilities of y2, y3, y4 and y5. For example, y2 and y3 are determined according to whether magnitude of a modulated symbol is greater or less than 4, and y4 and y5 are determined according to whether magnitude of a modulated symbol is closer to 4 or 0, centering on 2, or determined according to whether magnitude of a modulated symbol is closer 4 or 8, centering on 6. Therefore, a determining range of y2 and y3 is 4, and a determining range of y4 and y5 is 2. Thus, reliabilities of y2 and y3 are higher than reliabilities of y4 and y5. In sum, no-error probabilities, or reliabilities, of constituent bits of a modulation signal are R(y0)=R(y1)>R(y2)=R(y3)>R(y4)=R(y5).
In 64-QAM modulation, wherein 6 bits constitute a signal, 2 bits determine signs of a real part and an imaginary part of the signal, and 4 bits represent magnitudes of the real part and the imaginary part of the signal. Therefore, order of modulation signal (y0, y1, y2, y3, y4, y5) and roles of the constituent bits are subject to change. Even for a signal constellation of 256-QAM or higher, roles and reliabilities of modulation signal-constituting bits are changed in the same manner as above. That is, if one modulation signal is defined as (y0, y1, y2, y3, y4, y5, y6, y7), then R(y0)=R(y1)>R(y2)−R(y3)>R(y4)=R(y5)>R(y6)=R(y7).
Conventionally, however, when the communication system using LDPC codes performs interleaving/deinterleaving, the system uses an arbitrary interleaving/deinterleaving scheme regardless of the LDPC code or reliability characteristics of constituent bits of a high-order modulation signal, or uses an interleaving/deinterleaving scheme where only degrees of variable nodes or check nodes of the LDPC code are considered, thereby failing to minimize distortion of signals transmitted over a channel. In addition, as reliabilities of two consecutive constituent bits y2i and y2i+1 in a modulation signal are equal, the system recognizes the two bits as one bit group rather than recognizing them as two separate bits for a real part and an imaginary part. The limitation on recognition prevents maximization of the LDPC code's performance.